package my.suveng.leetcode.stack;

import java.util.Stack;

/**
 * 简化路径
 * @author suwenguang
 **/
public class S71 {

    public static void main(String[] args) {
        String path;
        String output;
        Solution solution = new Solution();

        path = "/home//foo/";
        output = solution.simplifyPath(path);
        System.out.println(output);


        path = "/a/../../b/../c//.//";
        output = solution.simplifyPath(path);
        System.out.println(output);

    }

    static class Solution {
        public String simplifyPath(String path) {
            return s2(path);
        }

        /**
         * 优化一下, 单栈
         * @author suwenguang
         */
        private String s2(String path) {
            StringBuilder res = new StringBuilder("/");
            String[] split = path.split("/");
            Stack<String> stack = new Stack<>();
            for (int i = 0; i < split.length; i++) {
                if (split[i].equals("") || split[i].equals(".")) {
                    continue;
                }

                if (split[i].equals("..")) {
                    if (!stack.isEmpty()) {
                        stack.pop();
                    }
                    continue;
                }

                stack.push(split[i]);
            }

            // java api 支持双遍历
            for (int i = 0; i < stack.size(); i++) {
                String pop = stack.get(i);
                res.append(pop);
                if (i + 1 < stack.size()) {
                    res.append("/");
                }
            }

            return res.toString();

        }

        /**
         * 自己写的双栈实现
         * @author suwenguang
         */
        private String s1(String path) {
            StringBuilder res = new StringBuilder("/");
            String[] split = path.split("/");
            Stack<String> stack = new Stack<>();
            for (int i = split.length - 1; i >= 0; i--) {
                if (split[i].equals("") || split[i].equals(".")) {
                    continue;
                }

                stack.push(split[i]);
            }


            Stack<String> output = new Stack<>();
            while (!stack.isEmpty()) {
                String pop = stack.pop();
                if (pop.equals("..")) {
                    if (!output.isEmpty()) {
                        output.pop();
                    }
                } else {
                    output.push(pop);
                }

            }

            while (!output.isEmpty()) {
                stack.push(output.pop());
            }

            while (!stack.isEmpty()) {
                String pop = stack.pop();
                res.append(pop);
                if (!stack.isEmpty()) {
                    res.append("/");
                }
            }

            return res.toString();
        }
    }
}
